#include <bits/stdc++.h>
using namespace std;
//堆排序的核心是建堆,传入参数为数组，根节点位置，数组长度
void Heap_build(vector<int>& a,int root,int length)
{
	int lchild = root*2+1;//根节点的左子结点下标
	if (lchild < length)//左子结点下标不能超出数组的长度
	{
		int max_value = lchild;//max_value保存左右节点中最大值的下标
		int rchild = lchild+1;//根节点的右子结点下标
		if (rchild < length)//右子结点下标不能超出数组的长度(如果有的话)
		{
			if (a[rchild] > a[max_value])//找出左右子结点中的最大值
				max_value = rchild;
		}
		if (a[root] < a[max_value])
		{
			//交换父结点和比父结点大的最大子节点
			swap(a[root],a[max_value]);
			//从此次最大子节点的那个位置开始递归建堆
			Heap_build(a,max_value,length);
		}
	}
}

void Heap_sort(vector<int>& a,int len)
{
	for (int i = len/2-1; i >= 0; --i)//从最后一个非叶子节点的父结点开始建堆
		Heap_build(a,i,len);

	for (int j = len-1; j > 0; --j)//j表示数组此时的长度，因为len长度已经建过了，从len-1开始
	{
		swap(a[0],a[j]);//交换首尾元素,将最大值交换到数组的最后位置保存
		Heap_build(a,0,j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2
	}

}
int main()
{
    vector<int>a = {5,23,16,68,94,72,71,84,76};
	Heap_sort(a,9);
 	for (int i = 0; i != 9; ++i)
 		cout<<a[i]<<" ";
	return 0;
}